/**
 * 单词搜索
 *
 * 描述
 * 给出一个二维字符数组和一个单词，判断单词是否在数组中出现，
 * 单词由相邻单元格的字母连接而成，相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。
 * 数据范围：
 * 0 < 行长度 <= 100
 * 0 < 列长度 <= 100
 * 0 < 单词长度 <= 1000
 *
 * 例如：
 * 给出的数组为["XYZE","SFZS","XDEE"]时，
 * 对应的二维字符数组为：
 * 若单词为"XYZZED"时，应该返回 true，
 * 也即：
 * 若单词为"SEE"时，应该返回 true，
 * 也即：
 * 若单词为"XYZY"时，应该返回 false。
 */

/**
 * 这里我们只要找到数组中的第一个字符, 然后开始深搜他就可以了
 * 记住, 要用一个数组标记这个位置是否已经找过
 * 还可以用剪枝来优化
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {

    // 全局变量
    int m, n;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] vis;
    char[] word;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board string字符串一维数组
     * @param _word string字符串
     * @return bool布尔型
     */
    public boolean exist (String[] board, String _word) {

        // 初始化
        m = board.length;
        n = board[0].length();
        vis = new boolean[m][n];
        word = _word.toCharArray();

        // 搜索每一个 word[0]
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {

                // 找到的话, 深搜这个位置
                if(board[i].charAt(j) == word[0]) {

                    if(dfs(board, i, j, 0)) {

                        // 要是能成功深搜, 返回 true
                        return true;
                    }
                }
            }
        }

        // 不成功就返回 false
        return false;
    }

    /**
     *
     * @param board
     * @param i
     * @param j
     * @param pos 记录搜索到第几个位置了
     * @return
     */
    private boolean dfs (String[] board, int i, int j, int pos) {

        // 函数出口, 要是能找到最后一个, 返回 true
        if(pos == word.length - 1) {
            return true;
        }

        // 标记这个位置已经找过
        vis[i][j] = true;

        for(int k = 0; k < 4; k++) {

            // 旁边的下标
            int x = i + dx[k], y = j + dy[k];

            // 判断条件, 首先不能越界, 然后之前不能找过, 最后单词要一样
            if(x >= 0 && x < m
                    && y >= 0 && y < n
                    && !vis[x][y]
                    && board[x].charAt(y) == word[pos + 1]) {

                // 继续向下深搜, 这里可以用下剪枝, 要是已经找到了, 直接返回出去, 就不用在向下面找了
                if(dfs(board, x, y, pos + 1)) {
                    return true;
                }

            }
        }

        // 恢复现场
        vis[i][j] = false;

        // 没成功返回 false
        return false;
    }
}